import array
import math

import unittest




#def highestSetBit(value):
#        mask = 1<<31
#        count = 31
#
#        while count > 0:
#            if (value & mask) > 0:
#                break
#            mask = mask >> 1
#            count -= 1
#        return count
#
#def createBitTable():
#    data = {}
#
#    for i in range(256):
#        data[i] = highestSetBit(i)
#
#    return data


highestSetBitTable = \
    {0: 0, 1: 0, 2: 1, 3: 1, 4: 2, 5: 2, 6: 2, 7: 2, 8: 3, 9: 3, 10: 3, 11: 3, 12: 3, 13: 3, 14: 3, 15: 3, 16: 4, 17: 4,
     18: 4, 19: 4, 20: 4, 21: 4, 22: 4, 23: 4, 24: 4, 25: 4, 26: 4, 27: 4, 28: 4, 29: 4, 30: 4, 31: 4, 32: 5, 33: 5,
     34: 5, 35: 5, 36: 5, 37: 5, 38: 5, 39: 5, 40: 5, 41: 5, 42: 5, 43: 5, 44: 5, 45: 5, 46: 5, 47: 5, 48: 5, 49: 5,
     50: 5, 51: 5, 52: 5, 53: 5, 54: 5, 55: 5, 56: 5, 57: 5, 58: 5, 59: 5, 60: 5, 61: 5, 62: 5, 63: 5, 64: 6, 65: 6,
     66: 6, 67: 6, 68: 6, 69: 6, 70: 6, 71: 6, 72: 6, 73: 6, 74: 6, 75: 6, 76: 6, 77: 6, 78: 6, 79: 6, 80: 6, 81: 6,
     82: 6, 83: 6, 84: 6, 85: 6, 86: 6, 87: 6, 88: 6, 89: 6, 90: 6, 91: 6, 92: 6, 93: 6, 94: 6, 95: 6, 96: 6, 97: 6,
     98: 6, 99: 6, 100: 6, 101: 6, 102: 6, 103: 6, 104: 6, 105: 6, 106: 6, 107: 6, 108: 6, 109: 6, 110: 6, 111: 6,
     112: 6, 113: 6, 114: 6, 115: 6, 116: 6, 117: 6, 118: 6, 119: 6, 120: 6, 121: 6, 122: 6, 123: 6, 124: 6, 125: 6,
     126: 6, 127: 6, 128: 7, 129: 7, 130: 7, 131: 7, 132: 7, 133: 7, 134: 7, 135: 7, 136: 7, 137: 7, 138: 7, 139: 7,
     140: 7, 141: 7, 142: 7, 143: 7, 144: 7, 145: 7, 146: 7, 147: 7, 148: 7, 149: 7, 150: 7, 151: 7, 152: 7, 153: 7,
     154: 7, 155: 7, 156: 7, 157: 7, 158: 7, 159: 7, 160: 7, 161: 7, 162: 7, 163: 7, 164: 7, 165: 7, 166: 7, 167: 7,
     168: 7, 169: 7, 170: 7, 171: 7, 172: 7, 173: 7, 174: 7, 175: 7, 176: 7, 177: 7, 178: 7, 179: 7, 180: 7, 181: 7,
     182: 7, 183: 7, 184: 7, 185: 7, 186: 7, 187: 7, 188: 7, 189: 7, 190: 7, 191: 7, 192: 7, 193: 7, 194: 7, 195: 7,
     196: 7, 197: 7, 198: 7, 199: 7, 200: 7, 201: 7, 202: 7, 203: 7, 204: 7, 205: 7, 206: 7, 207: 7, 208: 7, 209: 7,
     210: 7, 211: 7, 212: 7, 213: 7, 214: 7, 215: 7, 216: 7, 217: 7, 218: 7, 219: 7, 220: 7, 221: 7, 222: 7, 223: 7,
     224: 7, 225: 7, 226: 7, 227: 7, 228: 7, 229: 7, 230: 7, 231: 7, 232: 7, 233: 7, 234: 7, 235: 7, 236: 7, 237: 7,
     238: 7, 239: 7, 240: 7, 241: 7, 242: 7, 243: 7, 244: 7, 245: 7, 246: 7, 247: 7, 248: 7, 249: 7, 250: 7, 251: 7,
     252: 7, 253: 7, 254: 7, 255: 7}



'''
Store bits in unsigned char array.
'''
class BitVector(object):


    def __init__(self, bitsCount):
        if bitsCount <= 0:
            raise ValueError("Incorrect bitsCount passed, should be positive value: %d "  % bitsCount)
        self.__itemSize = 32
        self.__capacity = bitsCount
        self.__bucketsCount = math.ceil(self.__capacity / self.__itemSize)
        self.__size = 0
        self.__data = array.array('L', [0] * self.__bucketsCount )

        actualItemSize = self.__data.itemsize

        if actualItemSize * 8 != self.__itemSize:
            raise ValueError("Incorrect item size")


    def getLastSetBit(self):
        for i in range(len(self.__data)-1, -1, -1):
            if self.__data[i] > 0:
                bucketsFromStartCount = i
                baseOffset = bucketsFromStartCount * self.__itemSize
                bucketOffset = self.__lastSetBitInBucket(bucketsFromStartCount)
                return baseOffset + bucketOffset

        return 0

    def __lastSetBitInBucket(self, bucket):

        value = self.__data[bucket]
        mask = 0xFF000000
        byteIndex = 3
        while mask > 0:

            # check highest set byte
            if (value & mask) > 0:
                key = (value & mask) >> (byteIndex*8)
                highestBitInByte = highestSetBitTable[key]
                return byteIndex*8 + highestBitInByte

            byteIndex -= 1
            mask = mask >> 8

        return 0

    def size(self):
        return self.__size

    def isEmpty(self):
        return self.__size == 0

    '''
    Added for tests, comment after finished
    '''
    @property
    def data(self):
        return self.__data

    def __iter__(self):
        self.__iteratorPos = 0
        return self


    def __next__(self):
        
        if self.__iteratorPos >= len(self):
            raise StopIteration

        while not self[self.__iteratorPos]:
            self.__iteratorPos += 1

        value = self.__iteratorPos
        self.__iteratorPos += 1

        return value


    def next(self):
        return self.__next__()

    '''
    Length of BitVector is equal lastSetBit
    '''
    def __len__(self):
        return self.getLastSetBit()

        '''
    Get bit value (True/False) in 'index' position.
    '''
    def __getitem__(self, index):
        self.__checkBoundaries(index)
        position = self.__findBucketAndOffset(index)
        return (self.__data[position[0]] & (1<<position[1]) > 0)

    def __setitem__(self, index, value):
        if value:
            self.__setBit(index)
        else:
            self.__clearBit(index)


    def __hash__(self):
        res = 37

        for i in range( len(self)+1):
            if self[i]:
                res = 31 * res + hash(i)

        return res

    def __eq__(self, other):
        if self is other:
            return True
        if other == None or type(self) != type(other):
            return False

        length = len(self)
        otherLength = len(other)

        if length != otherLength:
            return False

        for i in range(length):
            if self[i] != other[i]:
                return False

        return True

    def __repr__(self):
        return self.__str__()

    def __str__(self):
        strValue = "("

        length = len(self)

        for i in range( length+1 ):
            if self[i]:
                strValue += str(i)
                if i != length:
                    strValue += ", "
        strValue += ")"
        return strValue

    def clone(self):
        res = BitVector(self.__capacity)
        res.__data = self.__data[:]
        return res


    def __add__(self, other):

        if self is other:
            return self.clone()

        if type(self) != type(other):
            raise ValueError("Can't union BitVector with: " + type(other))

        bigger = self
        smaller = other

        if len(bigger) < len(smaller):
            bigger, smaller = smaller, bigger

        res = bigger.clone()

        for i in range(len(smaller.__data)):
            res.__data[i] |= smaller.__data[i]

        return res


    def __sub__(self, other):
        if self is other:
            return self.clone()

        if type(self) != type(other):
            raise ValueError("Can't subtract BitVector with: " + type(other))

        res = self.clone()
        length = len(self)

        # todo optimize this, make subtraction by chunks

        for i in range(len(other)):
            if i > length:
                break
            if other[i]:
                res[i] = False

        return res

    '''
    Set bit in 'index' position to True
    '''
    def __setBit(self, index):
        if not self[index]:
            position = self.__findBucketAndOffset(index)
            self.__data[position[0]] |= (1<<position[1])
            self.__size += 1

    '''
    Set bi to False at 'index' position.
    '''
    def __clearBit(self, index):
        if self[index]:
            position = self.__findBucketAndOffset(index)
            self.__data[position[0]] &= ~(1<<position[1])
            self.__size -= 1


    '''
    return tuple  (bucketIndex, offset)
    '''
    def __findBucketAndOffset(self, index):
         return (int(index / 32), index % 32)

    def __checkBoundaries(self, index):
        if index < 0:
            raise ValueError("Index can't be negative: " + str(index) )
        if index > self.__capacity:
            raise ValueError("Index is out of bounds, index = %d, should be in range [0, %d]" % (index, self.__capacity))





class BitVectorTest(unittest.TestCase):


    def testSubtract(self):
        vec1 = BitVector(10)
        vec1[1] = True
        vec1[3]= True
        vec1[6] = True
        vec1[9] = True

        vec2 = BitVector(20)
        vec2[3] = True
        vec2[4]= True
        vec2[6] = True
        vec2[12] = True
        vec2[15] = True

        res = vec1 - vec2

        self.assertTrue( res[1] )
        self.assertTrue( res[9] )
        self.assertFalse( res[3] )
        self.assertFalse( res[6] )

    def testClone(self):
        vec = BitVector(20)

        vec[5] = True
        vec[16] = True
        vec[19] = True

        vecClone = vec.clone()

        self.assertTrue( vecClone[5] )
        self.assertTrue( vecClone[16] )
        self.assertTrue( vecClone[19] )

        vec[8] = True

        self.assertTrue( vecClone[5] )
        self.assertTrue( vecClone[16] )
        self.assertTrue( vecClone[19] )
        self.assertFalse( vecClone[8] )

        vecClone[11] = True

        self.assertTrue( vec[5] )
        self.assertTrue( vec[8] )
        self.assertTrue( vec[16] )
        self.assertTrue( vec[19] )
        self.assertFalse( vec[11] )

    def testUnionSameLength(self):
        vec1 = BitVector(20)

        vec1[5] = True
        vec1[16] = True
        vec1[19] = True

        vec2 = BitVector(20)

        vec1[3] = True
        vec1[5] = True
        vec1[18] = True
        vec1[20] = True

        vec3 = vec1+vec2

        self.assertTrue( vec3[3] )
        self.assertTrue( vec3[5] )
        self.assertTrue( vec3[16] )
        self.assertTrue( vec3[18] )
        self.assertTrue( vec3[20] )

    def testIterator(self):

        vec = BitVector(20)

        vec[5] = True
        vec[6] = True
        vec[17] = True

        vecData = (5,6,17)
        index = 0

        for value in vec:
            self.assertEqual( vecData[index], value )
            index += 1

    def testEquality(self):
        vec1 = BitVector(10)
        vec2 = BitVector(10)

        self.assertTrue( vec1 == vec2 )

        vec1[6] = True

        self.assertFalse( vec1 == vec2 )

        vec1[3] = True
        vec2[6] = True

        self.assertFalse( vec1 == vec2 )

        vec2[3] = True

        self.assertTrue( vec1 == vec2 )

    def testStrAndRepr(self):
        vec = BitVector(100)


        vec[5] = True
        vec[34] = True
        vec[89] = True

        self.assertEqual("(5, 34, 89)", str(vec) )
        self.assertEqual("(5, 34, 89)", repr(vec))


    def testGetLastSetBit(self):
        vec = BitVector(100)
        self.assertEqual( 0, vec.getLastSetBit() )

        vec[86] = True
        self.assertTrue( vec[86] )
        self.assertEqual( 86, vec.getLastSetBit() )

        vec[99] = True
        self.assertTrue( vec[99] )
        self.assertEqual( 99, vec.getLastSetBit() )

        vec[100] = True
        self.assertEqual( 100, vec.getLastSetBit() )


    def testCreateWithIncorrectBitsCount(self):

        try:
            BitVector(-50)
            self.fail("ValueError wasn't thrown")
        except ValueError:
            pass
        except Exception as ex:
            raise AssertionError("Incorrect exception was thrown")

        try:
            BitVector(0)
            self.fail("ValueError wasn't thrown")
        except ValueError:
            pass
        except Exception as ex:
            raise AssertionError("Incorrect exception was thrown")
        

    def testCreate(self):
        vec = BitVector(100)
        self.assertEqual( 4, len(vec.data) )
        self.assertEqual( 0, vec.size() )
        self.assertEqual( 0, len(vec) )

        for i in range(len(vec.data)):
            self.assertEqual(0, vec.data[i])

        vec = BitVector(3)
        self.assertEqual( 1, len(vec.data) )
        self.assertEqual( 0, vec.size() )
        self.assertEqual( 0, len(vec) )

        for i in range(len(vec.data)):
            self.assertEqual(0, vec.data[i])

    def testClearBits(self):
        vec = BitVector(100)
        vec[10] = True
        vec[14] = True
        vec[15] = True


        self.assertEqual( 3, vec.size() )
        self.assertFalse( vec.isEmpty() )
        self.assertTrue( vec[10])
        self.assertTrue( vec[14])
        self.assertTrue( vec[15])

        vec[10] = False

        self.assertEqual( 2, vec.size() )
        self.assertFalse( vec.isEmpty() )
        self.assertFalse( vec[10] )
        self.assertTrue( vec[14])
        self.assertTrue( vec[15])

        vec[14] = False

        self.assertEqual( 1, vec.size() )
        self.assertFalse( vec.isEmpty() )
        self.assertFalse( vec[10] )
        self.assertFalse( vec[14])
        self.assertTrue( vec[15])

        vec[15] = False

        self.assertEqual( 0, vec.size() )
        self.assertTrue( vec.isEmpty() )
        self.assertFalse( vec[10] )
        self.assertFalse( vec[14])
        self.assertFalse( vec[15])

    def testSetBitsOutOfBoundaries(self):
        vec = BitVector(50)

        try:
            vec[55] = True
            self.fail("ValueError wasn't thrown")
        except ValueError:
            pass
        except Exception as ex:
            raise AssertionError("Incorrect exception was thrown")

        try:
            vec[51] = True
            self.fail("ValueError wasn't thrown")
        except ValueError:
            pass
        except Exception as ex:
            raise AssertionError("Incorrect exception was thrown")

        try:
            vec[-1] = True
            self.fail("ValueError wasn't thrown")
        except ValueError:
            pass
        except Exception as ex:
            raise AssertionError("Incorrect exception was thrown")

    def testSetBits(self):
        vec = BitVector(100)

        self.assertEqual(0, vec.size())
        self.assertTrue( vec.isEmpty() )
        self.assertFalse( vec[0] )
        self.assertFalse( vec[6] )
        self.assertFalse( vec[7] )
        self.assertFalse( vec[8] )
        self.assertFalse( vec[75] )

        vec[7] = True

        self.assertEqual(1, vec.size())
        self.assertFalse( vec.isEmpty() )
        self.assertFalse( vec[0] )
        self.assertFalse( vec[6] )
        self.assertTrue( vec[7] )
        self.assertFalse( vec[8] )
        self.assertFalse( vec[75] )

        vec[75] = True

        self.assertEqual(2, vec.size())
        self.assertFalse( vec.isEmpty() )
        self.assertFalse( vec[0] )
        self.assertFalse( vec[6] )
        self.assertTrue( vec[7] )
        self.assertFalse( vec[8] )
        self.assertTrue( vec[75] )

    def testSetBitsNearBoundaries(self):
        vec = BitVector(100)
        
        self.assertFalse( vec[0] )
        self.assertFalse( vec[100])

        vec[0] = True

        self.assertTrue( vec[0] )
        self.assertFalse( vec[100])

        vec[100] = True

        self.assertTrue( vec[0] )
        self.assertTrue( vec[100])



if __name__ == "__main__":
    unittest.main(BitVectorTest)
